__author__ = 'st316'
'''
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
'''


# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

    def toString(self):
        cur = self
        s = ''
        while cur.next:
            s += str(cur.val) + ' -> '
            cur = cur.next
        return s + str(cur.val)


class Solution:
    # @param a list of ListNode
    # @return a ListNode
    def mergeKLists(self, lists):
        if not lists:
            return None
        if len(lists) == 1:
            return lists[0]
        i = 0
        r = []
        while i < len(lists) - 1:
            r.append(self.merge2Lists(lists[i], lists[i + 1]))
            i += 2
        if len(lists) % 2 == 1:
            r.append(lists[-1])
        return self.mergeKLists(r)

    def merge2Lists(self, listA, listB):
        if not listA:
            return listB
        if not listB:
            return listA
        head = ListNode(-1)
        cur = head
        p = listA
        q = listB
        while p and q:
            if p.val < q.val:
                cur.next = p
                p = p.next
            else:
                cur.next = q
                q = q.next
            cur = cur.next
        cur.next = p if p else q
        return head.next


if __name__ == '__main__':
    l = [1, 2, 3, 4, 5]
    l1 = ListNode(l[0])
    cur1 = l1
    for v in l[1:]:
        cur1.next = ListNode(v)
        cur1 = cur1.next

    l = [2, 3, 4, 5, 6, 7, 8]
    l2 = ListNode(l[0])
    cur2 = l2
    for v in l[1:]:
        cur2.next = ListNode(v)
        cur2 = cur2.next

    l = [10, 16]
    l3 = ListNode(l[0])
    cur = l3
    for v in l[1:]:
        cur.next = ListNode(v)
        cur = cur.next
    s = Solution()
    print s.mergeKLists([l1, l2, l3]).toString()